package com.pointstar.dp.queue;


import com.pointstar.dp.tree.BinarySearch;

import java.util.stream.IntStream;

/**
 * 南软2013BT1
 * 二叉搜索树实现优先队列
 *
 * @author 朱科睿
 */
public class PriorityQueue {

    private BinarySearch root;
    private int size;

    public PriorityQueue() {
        this.root = new BinarySearch();
        this.size = 0;
    }

    /**
     * 查找待插入值的节点位置
     *
     * @param root 根节点
     * @param data 指定值
     * @return 查找结果
     */
    private BinarySearch find(BinarySearch root, int data) {
        //如果待插入的值在队列中已经存在，则默认插入到右子树
        if (data == root.getData()) {
            BinarySearch right = new BinarySearch();
            root.setRight(right);
            return right;
        }
        if (data > root.getData()) {
            if (root.getRight() == null) {
                BinarySearch right = new BinarySearch();
                root.setRight(right);
                return right;
            }
            return find(root.getRight(), data);
        }
        if (root.getLeft() == null) {
            BinarySearch left = new BinarySearch();
            root.setLeft(left);
            return left;
        }
        return find(root.getLeft(), data);
    }

    /**
     * 插入节点
     *
     * @param data 新元素
     */
    private void insert(int data) {
        if (size == 0) {
            root.setData(data);
        } else {
            BinarySearch node = find(root, data);
            node.setData(data);
        }
        size++;
    }

    /**
     * 查找以指定节点为根节点的树的最大值的父节点
     *
     * @param root 指定根节点
     * @return 以指定节点为根节点的树的最大值的父节点
     */
    private BinarySearch findMaxParentNode(BinarySearch root) {
        if (root.getRight() == null) {
            return root;
        }
        if (root.getRight().getRight() == null) {
            return root;
        }
        return findMaxParentNode(root.getRight());
    }

    /**
     * 删除节点
     *
     * @return 被删除节点的值
     */
    private int delete() {
        BinarySearch maxParentNode = findMaxParentNode(root);
        int result;
        if (maxParentNode.getRight() == null) {
            result = maxParentNode.getData();
            root = maxParentNode.getLeft();
        } else {
            result = maxParentNode.getRight().getData();
            if (maxParentNode.getRight().getLeft() != null) {
                maxParentNode.setRight(maxParentNode.getRight().getLeft());
            } else {
                maxParentNode.setRight(null);
            }
            size--;
        }
        return result;
    }

    public static void main(String[] args) {
        PriorityQueue queue = new PriorityQueue();
        queue.insert(88);
        queue.insert(88);
        queue.insert(152);
        queue.insert(1);
        queue.insert(66);
        queue.insert(41);
        queue.insert(41);
        queue.insert(7);
        queue.insert(818);
        queue.insert(102);
        queue.insert(122);
        queue.insert(44);
        queue.insert(882);
        queue.insert(67);
        IntStream.range(0, queue.size).map(i -> queue.delete()).forEach(System.out::println);
    }

}